/**
 * 20. Valid Parentheses
 * https://leetcode.com/problems/valid-parentheses/
 */
package lc20;

import java.util.EmptyStackException;
import java.util.Stack;

public class Main {
  public static void main(String[] args) {
    String s = "}";
    boolean result = new Solution().isValid(s);
    System.out.println(result);
  }
}

class Solution {
  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    int n = s.length();
    for (int i = 0; i < n; i++) {
      char c = s.charAt(i);
      try {
        if (c == '}') {
          if (stack.pop().equals('{')) {
            continue;
          } else {
            return false;
          }
        } else if (c == ']') {
          if (stack.pop().equals('[')) {
            continue;
          } else {
            return false;
          }
        } else if (c == ')') {
          if (stack.pop().equals('(')) {
            continue;
          } else {
            return false;
          }
        } else {
          stack.push(c);
        }
      } catch (EmptyStackException e) {
        return false;
      }
    }
    if (stack.isEmpty()) {
      return true;
    }
    return false;
  }
}
